/*
 * Copyright (c) 2007, Nathan Sturtevant
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above copyright
 *       notice, this list of conditions and the following disclaimer in the
 *       documentation and/or other materials provided with the distribution.
 *     * Neither the name of the University of Alberta nor the
 *       names of its contributors may be used to endorse or promote products
 *       derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY NATHAN STURTEVANT ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <copyright holder> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
package com.googlecode.pathmachine.mm;

import java.util.ArrayList;
import java.util.List;

/**
 * MapSearchEnvironment
 *
 * This is an implementation of a search environment for performing searches
 * on maps. 32-bit nodes are mapped to maps using 16 bits for each of the x-
 * and y-coordinates
 * 
 * @author Nathan Sturtevant
 * @author <a href="mailto:eriq.adams@gmail.com">Eriq Muhammad Adams J.</a>
 */
public class MapSearchEnvironment extends SearchEnvironment {

    private Map map;

    public MapSearchEnvironment(Map map) {
        this.map = map;
    }

    @Override
    public double HCost(int node1, int node2) {
        int x1, x2, y1, y2;
        x1 = node1 >> 16;
        y1 = node1 & 0xFFFF;
        x2 = node2 >> 16;
        y2 = node2 & 0xFFFF;
        double a = ((x1 > x2) ? (x1 - x2) : (x2 - x1));
        double b = ((y1 > y2) ? (y1 - y2) : (y2 - y1));
        return (a > b) ? (b * Map.ROOT_TWO + a - b) : (a * Map.ROOT_TWO + b - a);
    }

    @Override
    public List<Integer> getNeighbors(int nodeID) {
        List<Integer> neighbors = new ArrayList<Integer>();
        int x1, y1;
        boolean up = false, down = false;
        x1 = nodeID >> 16;
        y1 = nodeID & 0xFFFF;

        if ((map.getTerrainType(x1, y1 + 1) == TTerrain.kGround)) {
            down = true;
            neighbors.add((x1 << 16) | (y1 + 1));
        }
        if ((map.getTerrainType(x1, y1 - 1) == TTerrain.kGround)) {
            up = true;
            neighbors.add((x1 << 16) | (y1 - 1));
        }
        if ((map.getTerrainType(x1 - 1, y1) == TTerrain.kGround)) {
            if ((up && (map.getTerrainType(x1 - 1, y1 - 1) == TTerrain.kGround))) {
                neighbors.add(((x1 - 1) << 16) | (y1 - 1));
            }
            if ((down && (map.getTerrainType(x1 - 1, y1 + 1) == TTerrain.kGround))) {
                neighbors.add(((x1 - 1) << 16) | (y1 + 1));
            }
            neighbors.add(((x1 - 1) << 16) | y1);
        }
        if ((map.getTerrainType(x1 + 1, y1) == TTerrain.kGround)) {
            if ((up && (map.getTerrainType(x1 + 1, y1 - 1) == TTerrain.kGround))) {
                neighbors.add(((x1 + 1) << 16) | (y1 - 1));
            }
            if ((down && (map.getTerrainType(x1 + 1, y1 + 1) == TTerrain.kGround))) {
                neighbors.add(((x1 + 1) << 16) | (y1 + 1));
            }
            neighbors.add(((x1 + 1) << 16) | y1);
        }
        return neighbors;
    }
}
